Матч 360, Сумма выбранных ячеек (SumOfSelectedCells)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Имеется прямоугольная таблица, в каждой ячейке которой записано целое число. Джесси выбирает наибольшее количество клеток так, чтобы в каждой строке и каждом столбце было выбрано не более одной клетки. Джесси высказала гипотезу: “независимо от выбора клеток сумма чисел, находящаяся в них, всегда одинакова”. По таблице, заданной в массиве table, выяснить, верна ли гипотеза Джесси, вернув соответственно “CORRECT” или “INCORRECT”.

Класс: SumOfSelectedCells

Метод: string hypothesis(vector<string> table)

Ограничения: table содержит от 1 до 20 элементов, элементы table содержат одинаковое количество записей, числа в которых изменяются от 1 до 50, строка table[i] содержит от 1 до 20 чисел.

Вход. Массив строк table, содержащий значения ячеек прямоугольной таблицы.

Выход. Строка “CORRECT” или “INCORRECT” в зависимости от справедливости гипотезы Джесси.

Пример входа

table

{"5 6 6"}

{"11 12 13 14",

"21 22 23 24",

"31 32 33 34",

"41 42 43 44"}

{"3 7",

"3 7",

"3 7"}

Пример выхода

“INCORRECT”

“CORRECT”

“CORRECT”

РЕШЕНИЕ

математика

Рассмотрим случай, когда ширина таблицы больше высоты. Тогда количество ячеек, выбранных Джесси, будет равняться высоте таблицы. В любой строке вместо выбранного элемента можно всегда выбрать такой элемент в этой же строке, который стоит в столбце, где нет выбранных элементов. Таким образом, для выполнения гипотезы таблица должна иметь вид:

A₁ A₁ A₁ ... A₁ A₁

A₂ A₂ A₂ ... A₂ A₂

.

.

A_H A_H A_H ... A_H A_H

То есть каждая строка должна содержать одинаковые элементы. Аналогично если высота таблицы больше ширины, то для выполнения гипотезы таблица должна иметь вид:

A₁ A₂ ... A_W

A₁ A₂ ... A_W

A₁ A₂ ... A_W

.

.

A₁ A₂ ... A_W

A₁ A₂ ... A_W

Рассмотрим теперь случай квадратной таблицы. Выберем четыре ячейки A_ip, A_jp, A_iq, A_jq, стоящие на пересечении двух строк и двух столбцов. Пусть A_ip + A_jq ≠ A_jp + A_iq. Тогда если среди выбранных имеются ячейки A_ip и A_jq, то заменив их на A_jp и A_iq, мы изменим общую сумму. Следовательно, все подобные суммы должны быть одинаковыми. То есть для любых i и j должно выполняться равенство: A₁₁ + A_ij = A_i1 + A_1j, из которого следует, что первая строка и первый столбец однозначно определяют все остальные числа таблицы.

Для решения задачи остается вычислить длину и ширину таблицы и в зависимости от них проверить, имеет ли таблица соответствующий тип.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <sstream>

using namespace std;

class SumOfSelectedCells

{

public:

string hypothesis(vector<string> table)

{

int i, j, s, n = table.size(), m;

vector<vector<int> > v(n);

for(i = 0; i < n; i++)

{

stringstream in(table[i]);

while (in >> s) v[i].push_back(s);

}

m = v[0].size();

if(n == m)

{

for(i = 1; i < n; ++i)

{

for(j = 1; j < n; ++j)

{

if (v[0][0] + v[i][j] != v[i][0] + v[0][j])

return "INCORRECT";

}

}

return "CORRECT";

}

if(n > m)

{

for(i = 0; i < m; ++i)

{

for(j = 1; j < n; ++j)

{

if (v[j][i] != v[0][i])

return "INCORRECT";

}

}

return "CORRECT";

}

else

{

for(i = 1; i < m; ++i)

{

for(j = 0; j < n; ++j)

{

if (v[j][i] != v[j][0])

return "INCORRECT";

}

}

return "CORRECT";

}

}

};